package com.qiangqiang.task.server.ranking;

import com.qiangqiang.task.server.ranking.entity.RankingUser;
import org.springframework.stereotype.Service;

import java.util.ArrayList;

/**
 * @program: task
 * @description: 树状分区算法实现排行榜：
 * <p>
 * [0,2000)
 * [0,1000)           [1000,2000]
 * [0,500) [500,1000)  [1000,1500)   [1500,2000)
 * ...  ... ...  ...  ...    ...   ...      ...
 * <p>
 * 在叶子节点用双向链表维持
 * @author: Sky.lin
 * @create: 2019-02-12 00:38
 **/
@Service
public class RankingTree {

    private class RankingNode {
        public int lowerKey = 0; // 低区间
        public int upperKey = 0; // 高区间
        public int number = 0;   // 在该区间中有多少人，用于实时计算用户排名

        public ArrayList<RankingUser> userList = new ArrayList<>(); // 在叶子节点中保存用户信息
        public RankingNode left = null;
        public RankingNode right = null;

        public RankingNode prev = null;
        public RankingNode next = null;

    }

    RankingNode root = null;

    RankingNode head = null;
    RankingNode tail = null;

    /**
     * @Description: 初始化线段树，[0,2000)
     * @Param:
     * @return:
     * @Author: sky.lin
     * @Date: 2019/2/12
     */
    public void setup(int lowerKey, int upperkey) {
        root = setupNode(root, lowerKey, upperkey);
    }

    /**
     * @Description: 新增一个用户，将其插入到线段树中
     * @Param:
     * @return:
     * @Author: sky.lin
     * @Date: 2019/2/12
     */
    public void insert(int score, RankingUser rankingUser) {
        insertIntoNode(root, score, rankingUser);
    }

    public void remove(int score, RankingUser rankingUser) {
        removeFromNode(root, score, rankingUser);
    }

    /**
     * @Description: 当一个用户成就值改变，则实时更新其排名
     * @Param:
     * @return:
     * @Author: sky.lin
     * @Date: 2019/2/12
     */
    public void change(int oldKey, int newKey, RankingUser rankingUser) {
        remove(oldKey, rankingUser);
        insert(newKey, rankingUser);
    }

    /**
     * @Description: 实时获得某个用户的排名
     * @Param:
     * @return:
     * @Author: sky.lin
     * @Date: 2019/2/12
     */
    public int getRanking(int score, RankingUser rankingUser) {
        return getRankingOfNode(root, score, rankingUser) + 1;
    }

    /**
     * @Description: 得到Top N 的用户
     * @Param:
     * @return:
     * @Author: sky.lin
     * @Date: 2019/2/12
     */
    public ArrayList<RankingUser> getTopN(int n) {
        ArrayList<RankingUser> dataList = new ArrayList<>();
        int count = 0;
        RankingNode cursor = tail;
        while (cursor != null) {
            for (RankingUser item : cursor.userList) {
                item.setRanking(++count);
                dataList.add(item);
                if (count >= n)
                    return dataList;
            }
            cursor = cursor.prev;
        }
        return dataList;
    }

    private int getRankingOfNode(RankingNode node, int score, RankingUser rankingUser) {
        int ranking = 0;
        if (node == null)
            return ranking;
        if (score < node.lowerKey) {
            ranking += node.number;
            return ranking;
        }
        if (score > node.upperKey) {
            ranking += 0;
            return ranking;
        }

        if (isLeafNode(node)) {
            ranking += Math.max(node.userList.indexOf(rankingUser), 0);
            return ranking;
        }
        final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);
        if (score <= middleKey) {
            ranking += node.right != null ? node.right.number : 0;
            ranking += getRankingOfNode(node.left, score, rankingUser);
        } else {
            ranking += getRankingOfNode(node.right, score, rankingUser);
        }
        return ranking;
    }

    private void removeFromNode(RankingNode node, int score, RankingUser rankingUser) {
        if (node == null)
            return;
        if (!isInsertNode(node, score))
            return;
        --node.number;
        if (isLeafNode(node)) {
            node.userList.remove(rankingUser);
            node.userList.sort(Comparators.getComparator());
            return;
        }

        final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);
        if (score <= middleKey)
            removeFromNode(node.left, score, rankingUser);
        else
            removeFromNode(node.right, score, rankingUser);
    }

    private void insertIntoNode(RankingNode node, int score, RankingUser rankingUser) {
        if (node == null)
            return;
        if (!isInsertNode(node, score))
            return;
        ++node.number;
        if (isLeafNode(node)) {
            node.userList.add(rankingUser);
            node.userList.sort(Comparators.getComparator());
            return;
        }
        final int middleKey = getMiddleKey(node.lowerKey, node.upperKey);
        if (score <= middleKey)
            insertIntoNode(node.left, score, rankingUser);
        else
            insertIntoNode(node.right, score, rankingUser);
    }


    private RankingNode setupNode(RankingNode node, int lowerKey, int upperkey) {
        if (lowerKey > upperkey) {
            return null;
        }
        node = new RankingNode();
        node.lowerKey = lowerKey;
        node.upperKey = upperkey;
        node.number = 0;
        node.userList.clear();

        if (isLeafNode(node)) {
            if (head == null)
                head = node;
            if (tail != null) {
                tail.next = node;
                node.prev = tail;
            }
            tail = node;
            return node;
        }

        if (upperkey > lowerKey) {
            final int middleKey = getMiddleKey(lowerKey, upperkey);
            node.left = setupNode(node.left, lowerKey, middleKey);
            node.right = setupNode(node.right, middleKey + 1, upperkey);
        }
        return node;
    }

    private boolean isInsertNode(RankingNode node, int score) {
        return score >= node.lowerKey && score <= node.upperKey;
    }

    private int getMiddleKey(int lowerKey, int upperkey) {
        return lowerKey + ((upperkey - lowerKey) >> 1); // l+(h-l)/2
    }

    private boolean isLeafNode(RankingNode node) {
        return node.lowerKey == node.upperKey;
    }
}
